package com.mzy;

import java.util.Arrays;
import java.util.Objects;

public class Comp {

    public static void insertSort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        int N = arr.length;
        for (int i = 1; i < N; i++) {
            int newIndex = i;
            while (newIndex > 0 && arr[newIndex - 1] > arr[newIndex]) {
                swap(arr, newIndex - 1, newIndex);
                newIndex--;
            }
        }
    }

    public static void selectSort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        int N = arr.length;
        int minIndex;

        for (int i = 0; i < N; i++) {
            minIndex = i;
            for (int j = i + 1; j < N; j++) {
                if (arr[minIndex] > arr[j]) {
                    minIndex = j;
                }
            }
            swap(arr, i, minIndex);
        }
    }

    // 返回一个数组arr, arr的长度在[1,maxLen-1],arr中的值在[0,maxValue-1]
    public static int[] lenRandomValueRandom(int maxLen, int maxValue) {
        int len = (int) (Math.random() * maxLen) + 1;
        int[] arr = new int[len];
        for (int i = 0; i < len; i++) {
            arr[i] = ((int) (Math.random() * maxValue));
        }
        return arr;
    }


    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static int[] copeArr(int[] arr) {
        int[] newArr = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            newArr[i] = arr[i];
        }
        return newArr;
    }

    // 判断当前数组是否是升序
    public static boolean isSored(int[] arr) {
        if (arr == null || arr.length == 0) {
            return false;
        }
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {

            if (max > arr[i]) {
                return false;
            }
            max = Math.max(max, arr[i]);
        }
        return true;
    }

    public static void main(String[] args) {
        // 测试 lenRandomValueRandom
        // int[] arr;
        // for (int i = 0; i < 100; i++) {
        //     arr = lenRandomValueRandom(10, 99);
        //     System.out.println(Arrays.toString(arr));
        // }

        for (int i = 0; i < 10000; i++) {
            int[] arr = lenRandomValueRandom(99, 1000);
            int[] newArr = copeArr(arr);
            insertSort(arr);
            selectSort(newArr);
            if (!isSored(arr)) {
                System.out.println(Arrays.toString(arr));
                System.out.println("插入排序错啦");
            }
            if (!isSored(newArr)) {
                System.out.println("选择排序错啦");

            }
        }

    }
}
